|
Space-filling trees are geometric constructions that are analogous to space-filling curves,〔Sagan, H. and J. Holbrook: "Space-filling curves", Springer-Verlag, New York, 1994〕 but have a branching, tree-like structure and are rooted. A space-filling tree is defined by an incremental process that results in a tree for which every point in the space has a finite-length path that converges to it. In contrast to space-filling curves, individual paths in the tree are short, allowing any part of the space to be quickly reached from the root. 〔Kuffner, J.J. and S.M. LaValle: ''Space-filling Trees'', The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.〕 〔Kuffner, J.J.; LaValle, S.M.; “Space-filling trees: A new perspective on incremental search for motion planning,” Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on , vol., no., pp.2199-2206, 25-30 Sept. 2011〕 The simplest examples of space-filling trees have a regular, self-similar, fractal structure, but can be generalized to non-regular and even randomized/Monte-Carlo variants (see Rapidly exploring random tree). Space-filling trees have interesting parallels in nature, including fluid distribution systems, vascular networks, and fractal plant growth, and many interesting connections to L-systems in computer science. ==Definition== A space-filling tree is defined by an iterative process whereby a single point in a continuous space is connected via a continuous path to every other point in the space by a path of finite length, and for every point in the space, there is at least one path that converges to it. The term "space-filling tree" in this sense was created in a 2009 tech report 〔Kuffner, J.J. and S.M. LaValle: ''Space-filling Trees'', The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.〕 that defines "space-filling" and "tree" differently than their traditional definitions in mathematics. As explained in the space-filling curve article, in 1890, Peano found the first space-filling curve, and by Jordan's 1887 definition, which is now standard, a curve is a single function, not a sequence of functions. The curve is "space filling" because it is "a curve whose range contains the entire 2-dimensional unit square" (as explained in the first sentence of space-filling curve). In contrast, a space-filling tree, as defined in the tech report, is not a single tree. It is only a sequence of trees. The paper says "A space-filling tree is actually defined as an infinite sequence of trees". It defines as a "sequence of trees", then states " is a space-filling tree". It is not space-filling in the standard sense of including the entire 2-dimensional unit square. Instead, the paper defines it as having trees in the sequence coming arbitrarily close to every point. It states "A tree sequence T is called 'space filling' in a space X if for every x in X, there exists a path in the tree that starts at the root and converges to x.". The standard term for this concept is that it includes a set of points that is dense everywhere in the unit square. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Space-filling tree」の詳細全文を読む スポンサード リンク
|